The problem can be found at the following link: Question Link
To find all critical connections in the graph, I used Tarjan's algorithm, which is based on depth-first search (DFS). Here's a brief explanation of the approach:
- Initialize variables
timer
,vis
,dis
,low
, andans
. - Implement a depth-first search (DFS) function to traverse the graph.
- During DFS traversal, mark the visited nodes and update the discovery time (
dis
) and lowest reachable node (low
) for each node. - If a backward edge is found (i.e.,
low[it] > dis[node]
), it indicates a critical connection. Store the edge in theans
vector. - Sort the
ans
vector to maintain order. - Return the
ans
vector containing all critical connections.
I personally recommend this video for detailed learning about Tarjan's algorithm.
-
Time Complexity : The time complexity of Tarjan's algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
-
Auxiliary Space Complexity : The auxiliary space complexity is
O(V + E)
, where V is the number of vertices and E is the number of edges in the graph. This space is utilized for maintaining thevis
,dis
,low
, andans
vectors.
class Solution {
public:
int timer = 0;
vector<vector<int>> ans;
vector<int> vis, dis, low;
void dfs(int node, int parent, vector<int> adj[]) {
++timer;
vis[node] = 1;
dis[node] = low[node] = timer;
for (auto it : adj[node]) {
if (it == parent)
continue;
else if (!vis[it])
dfs(it, node, adj);
low[node] = min(low[node], low[it]);
if (low[it] > dis[node])
ans.push_back({min(it, node), max(it, node)});
}
}
vector<vector<int>> criticalConnections(int v, vector<int> adj[]) {
vis = vector<int>(v, 0);
dis = low = vector<int>(v, -1);
for (int i = 0; i < v; i++) {
if (vis[i] == 0)
dfs(i, -1, adj);
}
sort(ans.begin(), ans.end());
return ans;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star to the getlost01/gfg-potd repository.